The present invention generally relates to image processing and, more particularly, to a method and device for fast SATD (Sum of Absolute Transformed Differences) estimation.
In recent years, it has become increasingly popular to transmit multimedia data, in particular, dynamic digital video data, via the Internet. Compression of digital video data is required for the transmission of multimedia data over bandwidth-constrained channels. To achieve efficient compression, complex, computationally intensive processes are used for encoding (i.e., compressing) and decoding (i.e., decompressing) the digital video data. For example, although MPEG-2 (Moving Pictures Expert Group, International Organization for Standards, Geneva, Switzerland) is known as an efficient technique for encoding video data, more efficient standards are being developed, such as the H.264/AVC (“Advanced Video Coding”) standard proposed by International Telecommunication Union Telecommunication Standardization Sector, Geneva, Switzerland.
The prediction mode of the H.264/AVC may be categorized into an inter mode and an intra mode. The inter mode is used to describe the temporal correlation between blocks within an image frame and a reference frame, while the intra mode is used to describe the spatial correlation between neighboring blocks within a same image frame. In the inter mode, a block of an image frame may be further divided into multiple blocks in accordance with seven partition modes, i.e., the inter 16×16, inter 16×8, inter 8×16, inter 8×8, inter 8×4, inter 4×8 and inter 4×4 modes. On the other hand, in the intra mode, the intra 16×16 and intra 4×4 modes are used as the partition modes. An encoder conducts a best-mode search to determine the encoding cost of each of the partition modes under the inter mode and the intra mode, respectively. The encoder then compares the inter mode that has the lowest encoding cost and the intra mode that has the lowest encoding cost to determine the final best mode. The above-mentioned process is typically called mode decision, which is the most computationally intensive task for an H. 264/AVC encoder.
In the H.264/AVC reference software, SATD (Sum of Absolute Transformed Differences) is used to determine the encoding cost. The SATD is usually the most important term and the largest computational load for making a mode decision. As compared to the conventional SAD (Sum of Absolute Differences), SATD is more precise in estimating the cost and provides better encoding quality. However, SATD may require larger computation capacity and a larger hardware budget due to its computation complexity.
The existing methods for fast SATD operation are generally directed to a Hadamard transform. Specifically, most of the existing methods are based on the FHT (Fast Hadamard Transform) algorithm, which is an FFT-like (Fast Fourier Transform) method. Other methods may be related to reducing the number of video samples taken or performing only a part of transform, which decreases the operation time at the sacrifice of SATD precision. It is therefore desirable to have a system and method to reduce the computation complexity and increase the speed in SATD operation without compromising the SATD performance.